/*
 * @lc app=leetcode.cn id=47 lang=cpp
 *
 * [47] 全排列 II
 */
#include <algorithm>
#include <unordered_map>
#include <vector>
using std::vector;
// @lc code=start
class Solution
{
  private:
    void permuteUnique_dfs(const vector<int> &nums, vector<int> &state, vector<bool> &visited, vector<vector<int>> &res)
    {

        if (state.size() == nums.size()) {
            std::for_each(state.cbegin(), state.cend(), [](int num) { std::cout << num << " "; });
            res.push_back(state);
            return;
        }

        std::unordered_map<int, bool> visited_map;
        for (int i = 0; i < nums.size(); ++i) {
            if (!visited_map.count(nums[i]) && !visited[i]) {
                visited_map[nums[i]] = true;
                visited[i] = true;
                state.push_back(nums[i]);
                permuteUnique_dfs(nums, state, visited, res);
                state.pop_back();
                visited[i] = false;
            }
        }
    }

  public:
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        vector<int> state;
        vector<vector<int>> res;
        vector<bool> visited(nums.size(), false);
        permuteUnique_dfs(nums, state, visited, res);
        return res;
    }
};
// @lc code=end
